#include<vector>
using namespace std;
class Solution {
    int row, col, tmp = 0, ret = 0;
    bool check[16][16] = { false };

public:
    int getMaximumGold(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] != 0) {
                    check[i][j] = true;
                    tmp += grid[i][j];
                    dfs(grid, i, j);
                    check[i][j] = false;
                    tmp -= grid[i][j];
                }
            }
        }
        return ret;
    }
    int xi[4] = { 0, 0, -1, 1 };
    int yj[4] = { 1, -1, 0, 0 };
    void dfs(vector<vector<int>>& grid, int i, int j) {
        for (int k = 0; k < 4; k++) {
            int x = xi[k] + i, y = yj[k] + j;
            if (x < row && y < col && x >= 0 && y >= 0 &&
                check[x][y] == false && grid[x][y] != 0) {
                tmp += grid[x][y];
                check[x][y] = true;
                dfs(grid, x, y);
                check[x][y] = false;
                tmp -= grid[x][y];
            }
        }
        if (tmp > ret)
            ret = tmp;
        return;
    }
};